Current Issue : July - September Volume : 2013 Issue Number : 3 Articles : 5 Articles
The maximum common connected edge subgraph problem is to find a connected\r\ngraph with the maximum number of edges that is isomorphic to a subgraph of each of the\r\ntwo input graphs, where it has applications in pattern recognition and chemistry. This paper\r\npresents a dynamic programming algorithm for the problem when the two input graphs\r\nare outerplanar graphs of a bounded vertex degree, where it is known that the problem is\r\nNP-hard, even for outerplanar graphs of an unbounded degree. Although the algorithm\r\nrepeatedly modifies input graphs, it is shown that the number of relevant subproblems is\r\npolynomially bounded, and thus, the algorithm works in polynomial time....
Data Mining is the process of obtaining high level knowledge by automatically discovering information from data in the form of rules and patterns. Data mining seeks to discover knowledge that is accurate, comprehensible and interesting. Association rule mining is a well established method of data mining that identifies significant correlations between items in transactional data. Measures like support count, comprehensibility and interestingness, used for evaluating a rule can be thought of as different objectives of association rule mining problem. In the thesis work we solve the association rule-mining problem using genetic algorithm. In the present work, we use the random sampling method. A perfect sample will improve the correctness of the rules generated by the algorithm. We will test in the approach only with the numerical valued attributes and must test with the categorical attributes also....
The dominating set problem is a core NP-hard problem in combinatorial\r\noptimization and graph theory, and has many important applications. Baker [JACM41,1994]\r\nintroduces a k-outer planar graph decomposition-based framework for designing polynomial\r\ntime approximation scheme (PTAS) for a class of NP-hard problems in planar graphs. It is\r\nmentioned that the framework can be applied to obtain an O(2ckn) time, c is a constant,\r\n(1+1/k)-approximation algorithm for the planar dominating set problem. We show that the\r\napproximation ratio achieved by the mentioned application of the framework is not bounded\r\nby any constant for the planar dominating set problem. We modify the application of the\r\nframework to give a PTAS for the planar dominating set problem. With k-outer planar graph\r\ndecompositions, the modified PTAS has an approximation ratio (1 + 2/k). Using 2k-outer\r\nplanar graph decompositions, the modified PTAS achieves the approximation ratio (1+1/k)\r\nin O(22ckn) time. We report a computational study on the modified PTAS. Our results show\r\nthat the modified PTAS is practical....
We study the problem of finding the minimum-length curvature constrained\r\nclosed path through a set of regions in the plane. This problem is referred to as the Dubins\r\nTraveling Salesperson Problem with Neighborhoods (DTSPN). An algorithm is presented\r\nthat uses sampling to cast this infinite dimensional combinatorial optimization problem as a\r\nGeneralized Traveling Salesperson Problem (GTSP) with intersecting node sets. The GTSP\r\nis then converted to an Asymmetric Traveling Salesperson Problem (ATSP) through a series\r\nof graph transformations, thus allowing the use of existing approximation algorithms. This\r\nalgorithm is shown to perform no worse than the best existing DTSPN algorithm and is\r\nshown to perform significantly better when the regions overlap. We report on the application\r\nof this algorithm to route an Unmanned Aerial Vehicle (UAV) equipped with a radio to\r\ncollect data from sparsely deployed ground sensors in a field demonstration of autonomous\r\ndetection, localization, and verification of multiple acoustic events....
Stock trading is a popular approach for money investment. Prediction of stock market trends has been an area of great interest both to researchers attempting to uncover the information hidden in the stock market data and for those who wish to profit by trading stocks. The extremely nonlinear nature of the stock market data makes it very difficult to design a system that can predict the future direction&n of the stock market with sufficient accuracy. The prediction of stock markets is an important and widely research issue since it could be had significant benefits and impacts, and the fuzzy rule based systems have been often utilized to forecast reasonably accurate predictions. For promoting the forecasting performance of fuzzy systems, this paper proposed a new model, which incorporates the concept of the decision tree,genetic algorithm and fuzzy systems . The Stock Market follows a Random Walk, which implies that the best prediction you can have about tomorrow''s value is today''s value. Here we are trying to predict the stock market close values by using a combinatorial method of vertical partion based decision tree and the genetic fuzzy rule based systems . The idea is to first apply the genetic algorithm to divide it a number of clusters and then by making a decision tree on the basis of the dataset, so that the prediction of the values is maximal....
Loading....